package heap

type BigHeap struct {
	count    int
	data     [] int
	capacity int
}

func NewBigHeap(capacity int) *BigHeap {

	return &BigHeap{count: 0, capacity: capacity, data: make([]int, capacity+1)}
}

func (this *BigHeap) insert(data int) {

	if this.count >= this.capacity {
		return
	}

	this.count++
	this.data[this.count] = data
	i := this.count
	for i/2 > 0 && this.data[i] > this.data[i/2] { // 自下往上堆化
		//交换下标为i和i/2的两个元素
		this.data[i], this.data[i/2] = this.data[i/2], this.data[i]
		i = i / 2
	}

}

func (this *BigHeap) get() int {

	if this.count <= 0 {
		return 0
	}

	return this.data[1]
}

func (this *BigHeap) geti(i int) int {

	if this.count <= 0 {
		return 0
	}

	return this.data[i]
}

func (this *BigHeap) remove(i int) {

	if this.count == 0 || this.capacity-i < 0 {
		return
	}

	//temp := this.data[i]
	this.data[i] = this.data[this.count]

	for {
		maxPos := i
		if i*2 <= this.count && this.data[i] > this.data[i*2] {
			maxPos = i * 2
		}
		if i*2+1 <= this.count && this.data[maxPos] > this.data[i*2+1] {
			maxPos = i*2 + 1
		}

		if maxPos == i {
			this.data[this.count] = 0
			this.count--
			break
		}

		this.data[i], this.data[maxPos] = this.data[maxPos], this.data[i]
		i = maxPos
	}
}

func (this *BigHeap) Sort() {

	a := this.data

	n := len(a) - 1
	k := n
	buildHeap(a, n)
	for k > 1 {

		a[1], a[k] = a[k], a[1]
		heapify(a, k-1, 1)
		k--
	}

}

func buildHeap(a [] int, n int) {
	for i := n / 2; i >= 1; i-- {
		heapify(a, n, i)
	}
}
func heapify(a [] int, n, i int) {

	for {
		maxPos := i
		if i*2 <= n && a[i] < a[i*2] {
			maxPos = i * 2
		}
		if i*2+1 <= n && a[maxPos] < a[i*2+1] {
			maxPos = i*2 + 1
		}

		if maxPos == i {

			break
		}
		a[i], a[maxPos] = a[maxPos], a[i]
		i = maxPos
	}
}
